package com.dxb.test.sort;

/**
 * 希尔排序
 * 基本思想：
 * 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
 * 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
 */
public class ShellSort extends BaseSort {

    public ShellSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {

        int temp = 0;
        int incre = length;

        while (true) {
            incre = incre / 2;
            //根据增量分为若干子序列
            for (int k = 0; k < incre; k++) {
                for (int i = k + incre; i < length; i += incre) {
                    int current = array[i];
                    int j = i - incre;
                    while (j >= 0 && array[j] > current) {
                        array[j + incre] = array[j];
                        j -= incre;
                    }
                    array[j + incre] = current;
                }
            }

            if (incre == 1) {
                break;
            }
        }
    }

    public static void main(String args[]) {
        int[] array = {99, 78, 26, 17, 82, 36, 9, 81, 22, 100, 30, 20, 17, 85};
        BaseSort qs = new ShellSort(array);
        qs.run();
    }
}
